import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class W61 {
    class SumIndex implements Comparable<SumIndex> {
        int sum;
        int num1;
        int num2;

        @Override
        public int compareTo(SumIndex o) {
            return this.sum - o.sum;
        }

        public SumIndex(int sum, int num1, int num2) {
            this.sum = sum;
            this.num1 = num1;
            this.num2 = num2;
        }
    }

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        int min1 = Math.min(length1, k);
        int min2 = Math.min(length2, k);
        PriorityQueue<SumIndex> sumQueue = new PriorityQueue<>();
        for (int i = 0; i < min1; i++) {
            for (int j = 0; j < min2; j++) {
                sumQueue.offer(new SumIndex(nums1[i]+nums2[j],nums1[i],nums2[j]));
            }
        }
        List<List<Integer>> result = new ArrayList<>(k);
        for (int i = 0; i < k&&!sumQueue.isEmpty(); i++) {
            SumIndex tempSum = sumQueue.poll();
            List<Integer> unit = new ArrayList<>(2);
            unit.add(tempSum.num1);
            unit.add(tempSum.num2);
            result.add(unit);
        }
        return result;
    }
}
